Wepresent an orchestration of the computations such that theoutcome isaccompanied withaproofofcorrectness thatcanbeverifiedwith substantially less computational resources than it takes to run the computations fromscratch withstate-of-the-art algorithms. Specifically,weadopt analgebraic proof system developed incomputational complexity theory,inwhich theproof is represented by a polynomial; evaluating the polynomial at a random point amounts to a verification of the proof with probabilistic guarantees.

PIBNET is hard for NP, by reduction from 3-satisfiability in the propositional calculus [3]. That classification has focused research on approximate methods, special-case techniques, heuristics, and analyses of average-case behavior. There now exists a number of algorithms for exact probabilistic inference in belief networks: the message-passing algorithm of Pearl [ 12], the triangulation method of Lauritzen and Spiegelhalter [10], and others. Previous approximation algorithms include the Markov-simulation scheme of Pearl [13, 14], Henrion's logic sampling [7], and the randomized approximation scheme (ras), known as BN-RAS, which we have previously demonstrated [1]. Heckerman has proposed a special-case algorithm for certain kinds of two-level belief networks [6]. Each algorithm has computational properties that render it attractive for inference on certain kinds of networks. The NPhard classification suggests, however, that no algorithm can provide a definitive efficient solution for all inference problems.

This note gives a simple analysis of a randomized approximation scheme for matrix multiplication proposed by Sarlos (2006) based on a random rotation followed by uniform column sampling. The result follows from a matrix version of Bernstein's inequality and a tail inequality for quadratic forms in subgaussian random vectors.